class Solution {
public:
    string hash[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    vector<string> ret;
    string path;
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return ret;
        dfs(digits, 0);
        return ret;
    }
    void dfs(string digits, int pos)
    {
        if (path.size() == digits.size())
        {
            ret.push_back(path);
            return;
        }
        for (auto& ch : hash[digits[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeSort(lists, 0, lists.size() - 1);
    }
    ListNode* mergeSort(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right) return nullptr;
        if (left == right) return lists[left];

        int mid = (left + right) / 2;
        ListNode* l1 = mergeSort(lists, left, mid);
        ListNode* l2 = mergeSort(lists, mid + 1, right);

        return mergeList(l1, l2);
    }
    ListNode* mergeList(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        ListNode* cur1 = l1, * cur2 = l2;
        ListNode newhead;
        newhead.next = nullptr;
        ListNode* prev = &newhead;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                prev = prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev = prev->next = cur2;
                cur2 = cur2->next;
            }
        }
        if (cur1) prev->next = cur1;
        if (cur2) prev->next = cur2;

        return  newhead.next;
    }
};